#环形链表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        a = b = head
        while b and b.next:
            a = a.next
            b = b.next.next
            if a == b:
                return True
        return False


#合并两个有序链表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        a = b = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                a.next, list1 = list1, list1.next
            else:
                a.next, list2 = list2, list2.next
            a = a.next
        a.next = list1 if list1 else list2
        return b.next



#二叉树的最大深度
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        q = [root]
        d = 0

        while q:
            t = []
            for i in q:
                if i.left:
                    t.append(i.left)
                if i.right:
                    t.append(i.right)
            q = t
            d += 1
        return d



#相同的树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True
        if (p == None and q != None) or (p != None and q == None):
            return False
        if p.val != q.val:
            return False

        left = self.isSameTree(p.left, q.left)
        right = self.isSameTree(p.right, q.right)

        return left and right


#翻转二叉树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        l1 = [root]
        l2 = []
        l3 = []
        while l1:
            n = len(l1)
            for i in range(n):
                a = l1[-1]
                l1.pop()
                l3.append(a)
                if a is None:
                    continue
                if a.left is not None:
                    l2.append(a.left)
                if a.right is not None:
                    l2.append(a.right)
                v = a.left
                a.left = a.right
                a.right = v
            l1 = l2.copy()
            l2 = []
        l1 = l3.copy()
        return root



#对称二叉树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        l = [root.left]
        r = [root.right]
        while l:
            a = l.pop(0)
            b = r.pop(0)
            if not a and not b:
                continue
            if not a or not b or a.val !=b.val:
                return False
            l.append(a.left)
            l.append(a.right)
            r.append(b.right)
            r.append(b.left)
        return not l or not r


#路径总和
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)


#完全二叉树的节点个数
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        num = 0
        a = [root]

        while a:
            b = a.pop()
            num += 1
            if b.left:
                a.append(b.left)
            if b.right:
                a.append(b.right)

        return num


#二叉树的层平均值
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        list =[]
        a = [root]
        while a:
            sum = 0
            k = 0
            l = len(a)
            for i in range(l):
                c = a.pop(0)
                sum += c.val
                k += 1
                if c.left:
                    a.append(c.left)
                if c.right:
                    a.append(c.right)
            v = sum/k
            list.append(v)
        return list




#二叉搜索树的最小绝对差
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def v(self, root, res):
        if root == None:
            return
        self.v(root.left, res)
        res.append(root.val)
        self.v(root.right, res)
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        res = []
        mina = float('inf')
        self.v(root, res)
        for i in range(len(res)-1):
            mina = min(abs(res[i+1]-res[i]), mina)
        return mina
